package com.dragon.datastructure.sort;

import java.util.Arrays;

/**
 * 希尔排序
 * 希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序
 * <p>
 * 希尔排序思想:
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;
 * 随着增量逐渐减少，每组包含的关键词越来越多，当增量减少至1时，整个文件恰好被分为一组，算法便终止
 *
 * @author dragon
 * @since 2019/12/23
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] array = new int[10];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 80);
        }
        long startTime = System.currentTimeMillis();
        sort3(array);
        long entTime = System.currentTimeMillis();
        System.out.println("希尔排序耗费的时间:" + (entTime - startTime) + "毫秒");
        System.out.println(Arrays.toString(array));
    }

    /**
     * 希尔排序(交换法) 排序耗费的时间:36020毫秒
     *
     * @param source 待排序的数组
     * @param <T>    数组中的元素类型
     */
    public static <T extends Comparable<T>> void sort(T[] source) {
        if (source == null || source.length < 2) {
            return;
        }
        for (int cap = source.length >> 1; cap > 0; cap >>= 1) {
            for (int i = cap; i < source.length; i++) {
                for (int j = i - cap; j >= 0; j -= cap) {
                    if (source[j].compareTo(source[j + cap]) > 0) {
                        T tmp = source[j];
                        source[j] = source[j + cap];
                        source[j + cap] = tmp;
                    }
                }
            }
        }
    }

    /**
     * 希尔排序移位法 排序耗费时间:88毫秒
     *
     * @param source 待排序的数组
     * @param <T>    数组中的元素类型
     */
    public static <T extends Comparable<T>> void sort2(T[] source) {
        if (source == null || source.length < 2) {
            return;
        }
        T insertValue;
        int insertIndex;
        // 分组
        for (int cap = source.length >> 1; cap > 0; cap >>= 1) {
            for (int i = cap; i < source.length; i++) {
                insertIndex = i;
                insertValue = source[insertIndex];
                // 如果insertValue 小于 他减去增量(cap)角标的的值，说明这个insertValue的位置还没有确定下来，它需要跟后面的元素进行比较，才能确定位置
                while (insertIndex - cap >= 0 && insertValue.compareTo(source[insertIndex - cap]) < 0) {
                    source[insertIndex] = source[insertIndex - cap];
                    insertIndex -= cap;
                }
                // 已经选好了插入的位置了，插入
                source[insertIndex] = insertValue;
            }
        }
    }



    public static void sort3(int[] source) {
        if (source == null || source.length < 2) {
            return;
        }
        // 分组
        for (int cap = source.length / 2; cap > 0; cap >>= 1) {
            for (int i = cap; i < source.length; i++) {
                int insertValue = source[i];
                int insertIndex = i;

                while (insertIndex - cap >= 0 && insertValue < source[insertIndex - cap]) {
                    source[insertIndex] = source[insertIndex - cap];
                    insertIndex -= cap;
                }
                // 说明换了位置
                if (insertIndex != i) {
                    source[insertIndex] = insertValue;
                }
            }
        }
    }
}
